package SortMethod;

import SortHelper.SortHelper;

import java.util.Random;

//通过快速排序来解决一个经典问题：找到一个数组中第k小的数。O(n)级别的算法
//利用暴力解决就是先排序然后再找
//高级思路就利用快速排序中的partition返回的数必定是当前数组第j小的数字，拿j和k比较，根据结果进行二分
public class SelectK {

    private SelectK(){}

    public static <E extends Comparable<E>> E selectK(E[] arr,int k){
        Random rnd = new Random();
        int whoK = selectK(arr,k,0,arr.length - 1,rnd);
        return arr[whoK];
    }

    private static <E extends Comparable<E>> int selectK(E[] arr, int k,int l , int r, Random rnd){
        if (k > arr.length-1) throw new RuntimeException("k值不合理");
        int p = partition(arr,l,r,rnd);
        while (true)
            if (p == k){
                return p;
            } else if (p > k){
                p = partition(arr,l,p-1,rnd);
            } else {
                p = partition(arr,p + 1,r,rnd);
            }
    }

    private static <E extends Comparable<E>> int partition(E[] arr, int l , int r, Random rnd){
        int p = l + rnd.nextInt(r - l + 1);
        SortHelper.swap(arr,p,l);
        int i = l + 1, j = r;
        while (true){
            while (i <= j && arr[i].compareTo(arr[l]) < 0)
                i++;
            while (j >= i && arr[j].compareTo(arr[l]) > 0)
                j--;
            if (i >= j) break;
            SortHelper.swap(arr,i,j);
            i++;
            j--;
        }
        SortHelper.swap(arr,l,j);
        return j;
    }

    //solution
    public static void main(String[] args) {
//        Random rnd = new Random();
        Integer[] arr = {2,6,5,3,1,6,7};
        Integer n =  selectK(arr,6);
        System.out.println(n);
    }
}
